Computing Permanents for Boson Sampling on Tianhe-2 Supercomputer

摘要

Boson sampling, a specific quantum computation problem, is widely regarded tobe one of the most achievable fields in which quantum machine will outperformthe most powerful classical computer in the near term, although up to now noupper-bound of how fast the classical computers can compute matrix permanents,core problem of Boson sampling, has been reported. Here we test the computingof the matrix permanent on Tianhe-2, a supercomputer retaining its position asthe world's No. 1 system for six times since June 2013. We arrived at the time(about 77.41~112.44 minutes) to compute the permanent of a $50\times 50$ matrixin an acceptable precision. In addition, we have found that Ryser's algorithmwill produce an unacceptable error with the increase of problem scale, comparedto Balasubramanian-Bax/Franklin-Glynn's algorithm in the same complexity. Theprecision issue suggests carefully check in future research of Boson sampling,and comprehensive comparison between quantum computer and classical computer.